package chapter07;

public class n_queen {
    static int n;
    static int[] x;
    static long sum;
    public static long nQueen(int n){
        n_queen.n=n;
        sum=0;
        x=new int[n+1];
        //backtrack2();
        backtrack(1);
        return sum;
    }
    public static boolean place(int k){
        for (int i = 1; i < k; i++) {
            if(Math.abs(k-i) == Math.abs(x[k]-x[i]) || x[i]==x[k])
                return false;
        }
        return true;
    }
    private static void backtrack(int t){
        if(t>n){
            sum++;
            print();
        }else {
            for (int i=1;i<=n;i++){
                x[t]=i;
                if(place(t))
                    backtrack(t+1);
            }
        }
    }
    private static void backtrack2(){
        x[1]=0;
        int k=1;
        while (k>0){
            x[k]+=1;
            while (x[k] <=n && !place(k))
                x[k]+=1;
            if(x[k]<=n){
                if(k==n)
                    sum++;
                else {
                    k++;
                    x[k]=0;
                }
            }else {
                k--;
            }
        }
    }
    public static void print(){
        for (int i = 1; i < x.length; i++) {
            System.out.print(x[i]);
        }
        System.out.println();
    }

    public static void main(String[] args) {

        long r=nQueen(8);
        System.out.println(r);

    }
}
